package 不同的子序列;

import java.util.Arrays;

/**
 * @author: AirMan
 * @date: 2025/5/19 11:09
 * @description:
 */
public class Solution2 {
    public int numDistinct(String s, String t) {
        // 找子序列出现的次数
        // ① dp数组及其下标含义：dp[i][j]表示t串中以下标 i-1 结尾的子串，s串中以下标 j-1 结尾的子序列，子串在子序列中出现的最大次数
        // ② 状态转移方程：如果当前字符相等，那么次数就等于不考虑当前两个字符的次数 + 不考虑s中这个字符但是考虑t中这个字符出现的次数
        //              如果当前字符不相等，那么次数就等于不考虑s字符，但是t字符任然是要考虑的
        //              dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
        //              dp[i][j] = dp[i][j - 1];
        // ③ dp数组的初始化：dp[0][i] = 1; 可以理解位t中取空串，那么在s中出现的次数就为1
        // ④ 遍历方向：从左上角到右下角


        int sLen = s.length();
        int tLen = t.length();

        int[] dp = new int[tLen + 1];

        dp[0] = 1;

        for (int i = 1; i <= sLen; i++) {
            dp[0] = 1;  // 表示t取空串，那么在s中总有一个方案
            int pre = dp[0]; // pre记录dp[i-1][j-1]
            for (int j = 1; j <= tLen; j++) {
                int cur = dp[j];
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[j] = pre + dp[j];
                }
                pre = cur;
            }
//            System.out.println(Arrays.toString(dp));
        }


        return dp[tLen];
    }
}
